package LeetCode;

import java.util.LinkedList;
import java.util.Stack;

public class LC_234_PalindromeLinkedList {

    public static void main(String[] args) {

    }

    static class Solution_1 {

        public static boolean isPalindrome(ListNode head) {
            LinkedList<Integer> nodeVal = new LinkedList<>();
            if (head == null || head.next == null)
                return true;
            ListNode slow = head;
            ListNode fast = head;
            nodeVal.add(0, slow.val);
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                nodeVal.add(0, slow.val);
            }
            ListNode cur = slow;
            if (fast.next != null)
                cur = slow.next;
            int i = 0;
            while (cur != null) {
                if (nodeVal.get(i) != cur.val)
                    return false;
                cur = cur.next;
                i++;
            }
            return true;
        }

    }


    static class Solution_2 {

        public static boolean isPalindrome(ListNode head) {
            Stack<ListNode> stack = new Stack<>();
            ListNode slow = head;
            ListNode fast = head;

            if (fast == null || fast.next == null) return true;

            stack.push(slow);
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                stack.push(slow);
            }
            if (fast.next != null)
                slow = slow.next;

            ListNode cur = slow;
            while (cur != null) {
                if (cur.val != stack.pop().val)
                    return false;
                cur = cur.next;
            }
            return true;
        }

    }
}